package io.github.hadyang.leetcode.random;

import org.junit.Test;

import java.util.LinkedList;

/**
 * 给定一个仅包含小写字母的字符串，去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
 *
 * <p>示例 1:
 *
 * <p>输入: "bcabc" 输出: "abc" 示例 2:
 *
 * <p>输入: "cbacdcbc" 输出: "acdb"
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/remove-duplicate-letters
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q316 {

  public String removeDuplicateLetters(String s) {
    if (s.length() == 0) return "";

    LinkedList<Character> stack = new LinkedList<>();
    stack.push('0');

    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
      count[s.charAt(i) - 'a']++;
    }

    for (int i = 0; i < s.length(); i++) {
      char target = s.charAt(i);
      count[target - 'a']--;

      if (stack.contains(target)) {
        continue;
      }

      while (!stack.isEmpty() && stack.peek() > target && count[stack.peek() - 'a'] != 0) {
        stack.pop();
      }
      stack.push(target);
    }

    StringBuilder builder = new StringBuilder();
    while (!stack.isEmpty()) {
      Character pop = stack.pop();
      if (pop == '0') continue;
      builder.append(pop);
    }

    return builder.reverse().toString();
  }

  @Test
  public void test() {
    System.out.println(removeDuplicateLetters("bcabc"));
    System.out.println(removeDuplicateLetters("cbacdcbc"));
    System.out.println(removeDuplicateLetters("c"));
    System.out.println(removeDuplicateLetters("baa"));
  }

  @Test
  public void test_long() {
    System.out.println(removeDuplicateLetters("rusrbofeggbbkyuyjsrzornpdguwzizqszpbicdquakqws"));
  }
}
